package nachos.vm;

import nachos.machine.*;
import nachos.threads.*;
import nachos.vm.*;

import java.util.*;

public class PageTable
{
	public PageTable()
	{
		invertedPageTable = new TranslationEntry[processor.getNumPhysPages()];
		
		for(int i = 0; i < processor.getNumPhysPages(); i++)
		{
			freePages.add(i);
		}

		// fill the page table with invalid entries
		for(int i = 0; i < Machine.processor().getNumPhysPages(); i++)
    	{
        	invertedPageTable[i] = new TranslationEntry(-1, i, false, false, false, false);
            // Adds entry to replacementList
	        replacementList.add(replacementIterator, invertedPageTable[i]);
    	}
        
        replacementList.clear();
	}

	public void addEntry(int pid, TranslationEntry t)
	{
		invertedPageTable[t.ppn] = t;
		long o = makeOwner(pid, t.vpn);
		Lib.assertTrue(t.vpn == getVpn(o));
		owner.put(o, t);		
	}

	public void removeEntry(long o)
	{
		if(owner.containsKey(o))
		{
			TranslationEntry t = owner.remove(o);
			invertedPageTable[t.ppn] = new TranslationEntry(-1, t.ppn, false, false, false, false);
			freePages.addLast(t.ppn);

			replacementList.remove(t);
			// Adds entry to replacementList
		        //replacementList.add(replacementIterator, invertedPageTable[t.ppn]);
			
		}
	}
	
	public void removeByPid(int pid)
	{
		ArrayList<Long> removes = new ArrayList<Long>();
		for(long o : owner.keySet())
		{
			if(pid == getPid(o))
			{
				removes.add(o);
			}
		}

		for(long o : removes)
		{
			removeEntry(o);
		}
	}

	public TranslationEntry getEntry(int pid, int vpn)
	{
		TranslationEntry t = owner.get(makeOwner(pid, vpn));
		// Nick: I don't think we need this assertion because if the entry is not found,
		// it means it is probably on disk and not in memory
		//Lib.assertTrue(t.vpn == vpn);
		return t;
	}
    
    public TranslationEntry getEntry(int ppn)
    {
        return invertedPageTable[ppn];
    }
    
    public void zeroPage(int ppn)
	{
		byte[] memory = Machine.processor().getMemory();
        int paddr = Processor.makeAddress(ppn, 0);
        Arrays.fill(memory, paddr, paddr+(Processor.pageSize-1), (byte)0);
	}

	public static long makeOwner(int pid, int vpn)
	{
		return ((long)pid << 32) | vpn;
	}

	public static int getPid(long owner)
	{
		return (int) (owner >> 32);
	}

	public static int getVpn(long owner)
	{
		return (int) (owner & 0xFFFFFFFFL);
	}
    
    public int getOwnerPid(int ppn)
	{
		for(Long o : owner.keySet())
		{
			if(owner.get(o).ppn == ppn)
			{
				return getPid(o);
			}
		}

		return -1;
	}

	protected LinkedList<Integer> freePages = new LinkedList<Integer>();
	protected Processor processor = Machine.processor();
	protected Hashtable<Long,TranslationEntry> owner = new Hashtable<Long,TranslationEntry>();
	protected TranslationEntry[] invertedPageTable = null;
	
    //Linked list used for clock page replacement algorithm
    protected LinkedList<TranslationEntry> replacementList = new LinkedList<TranslationEntry>();
    // List iterators for the linked lists
    protected ListIterator<TranslationEntry> replacementListIt = replacementList.listIterator();
    protected int replacementIterator = 0;
}
